package algo.sort;
// 大顶堆
// 数组下标0 不使用。
// 对于节点k:
// 父节点为 k/2
// 子节点为 2k， 2k+1
public class Heap<T extends Comparable<? super T>>{
    private T[] heap;
    private int N = 0;

    // 插入元素
    public void insert(T value) {
//    public void insert(Comparable value) {
        heap[++N] = value;
        swim(N);
    }

    // 删除最大元素
    public T delMax() {
        T max = heap[1];
/*
        swap(1, N--);
        heap[N + 1] = null;
*/
        swap(1, N);
        heap[N--] = null;
        sink(1);
        return max;
    }

    // 上浮
    private void swim(int k) {
        // 每当 k 不为堆顶，且父节点 k/2 比 k 小， 交换之
        while (k > 1 && less(k/2, k)) {
            swap(k/2, k);
            k /= 2;
        }
    }

    // 下沉
    private void sink(int k) {
        while (k*2 <= N) {
            int j = k*2;
            // 大顶堆
            // 子节点中找最大的, 因为一旦要让子节点上浮， 只能选择更大的那个子节点
            if (j < N && less(j, j+1))
                ++j;

            // 如果 k 的最大的子节点也比 k 小， 跳出
            if (!less(k, j))
                break;

            swap(k, j);
            k = j;
        }
    }
    public Heap(int maxLen) {
        this.heap = (T[]) new Comparable[maxLen + 1];
    }
    public boolean isEmpty() {
        return N == 0;
    }
    public int size() {
        return N;
    }
    private boolean less(int i, int j) {
        return heap[i].compareTo(heap[j]) < 0;
    }
    private boolean greater(int i, int j) {
        return heap[i].compareTo(heap[j]) > 0;
    }
    private void swap(int i, int j) {
        T t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }
}
